package ch18._08;

import java.util.*;

public class Solution {
	public static void main(String[] args) {
		String test = "mississippi";
		String[] list = {"mis", "is", "sip", "hi", "sis"};
		SuffixTree tree = new SuffixTree(test);
		for (String s : list) {
			List<Integer> indexes = tree.search(s);
			if (indexes == null) {
				System.err.println(s + ": String " + " not found.");
			} else {
				System.out.println(s + ": " + indexes.toString());
			}
		}
	}
}

class SuffixTreeNode {
	Map<Character, SuffixTreeNode> children;
	List<Integer> indexes;
	Character value;

	public SuffixTreeNode(Character ch) {
		this.value = ch;
		children = new HashMap<Character, SuffixTreeNode>();
		indexes = new ArrayList<Integer>();
	}

	public SuffixTreeNode() {
		this(null);
	}

	public void insertString(String s, int index) {
		indexes.add(index);
		if (s != null && s.length() > 0) {
			char firstChar = s.charAt(0);
			SuffixTreeNode child = null;
			if (children.containsKey(firstChar)) {
				child = children.get(firstChar);
			} else {
				child = new SuffixTreeNode(firstChar);
				children.put(firstChar, child);
			}
			String remainder = s.substring(1);
			child.insertString(remainder, index);
		}
	}

	public List<Integer> search(String s) {
		if (s == null || s.length() == 0) {
			return indexes;
		} else {
			char first = s.charAt(0);
			if (children.containsKey(first)) {
				/**
				 * Good Question.
				 * I am not very familiar with this kind of recursion.
				 * What a shame.
				 */
//				return search(s.substring(1));
				return children.get(first).
						search(s.substring(1));
			}
		}
		return null;
	}
}

class SuffixTree {

	private SuffixTreeNode root = new SuffixTreeNode();

	public SuffixTree(String s) {
		for (int i = 0; i < s.length(); i++) {
			root.insertString(s.substring(i), i);
		}
	}

	public List<Integer> search(String s) {
		return root.search(s);
	}
}